Analysis of Common Loops

Increasing counter

Python

for i in range(0, n, c):
    # some constant work

JavaScript

for (let i = 0; i < n; i += c) {
  // some constant work
}

Example: for n = 10 and c = 2, it will run 5 times (0, 2, 4, 6, 8).
Time complexity for this loop is $\Theta(\lfloor \frac{n}{c} \rfloor)$ . Ignoring constants, it’s $\Theta(n)$ .

Decreasing counter

Python

for i in range(n, 0, c) # where c is negative value
    # some constant work

JavaScript

for (let i = n; i > 0; i -= c) {
  // some constant work
}

Example: for n = 10 and c = 2, it will run 5 times (10, 8, 6, 4, 2).
Time complexity for this loop is $\Theta(\lceil \frac{n}{c} \rceil)$ . Ignoring constants, it’s $\Theta(n)$ .

Counter getting multiplied in each iteration

Python

i = 1
    while i < n:
        # some constant work
        i *= c

JavaScript

for (let i = 1; i < n; i *= c) {
  // some constant work
}

Example: For n = 32 and c = 2, it will be executed 5 times 1, 2, 4, 8, 16. For n = 33 and c = 2, it will be executed 6 times 1, 2, 4, 8, 16, 32. Generalizing, it runs for $1, c, c^2, c^3, ..., c^{k-1}$ i.e. it runs $$k$$ times from $$1$$ to $$k-1$$ .
$c^{k-1} < n \\ k-1 < \log_c n \\ k < \log_c n + 1$
So, the loop is going to run $\log_c n + 1$ times.
Time complexity for this loop is $\Theta(\log n)$ .
Note that base of the log doesn’t matter, since bases can be converted by simple multiplication or division operations and in asymptotic analysis constants are ignored.

Counter getting divided in each iteration

Python

i = n
    while i > 1:
        # some constant work
        i //= c # // is integer division

JavaScript

for (let i = n; i > 1; i /= c) {
  // some constant work
}

Example:
For n = 32 and c = 2, it will be executed 5 times 32, 16, 8, 4, 2. For n = 33 and c = 2, it will be executed 6 times 33, 16, 8, 4, 2`.
Time complexity for this loop is $\Theta(\log n)$ .

Counter raised to some power in each iteration

Python

i = 2
    while i < n:
        # some constant work
        i = pow(i, c)

JavaScript

for (let i = 2; i < n; i = Math.pow(i, c)) {
  // some constant work
}

Example: For c = 2 and n = 32 it’s going to run for $2, 2^2, {(2^2)}^2$ i.e. 2, 4, 16.

Let’s find out the number of times the loop runs:
$2, 2^c, {(2^c)}^c \\ 2, 2^c, 2^{c^2}, ...2^{c^{k-1}} \text{\footnotesize k is the number of times it runs} \\ 2^{c^{k-1}} < n \\ c^{k-1} < \log_2 n \\ k - 1 < \log_2 \log_2 n \\ k < \log_2 \log_2 n + 1$
Time complexity of this loop is $\Theta(\log\log n)$ .

Sequential loops

Python

def fun(n):
    for i in range(n):          # 𝛳(n)
        # some constant work
    i = 0
    while i < n:                # 𝛳(log n)
        # some constant work
        i *= 2
    for i in range(1, 100):     # 𝛳(1)
        # some constant work

JavaScript

function fun(n) {
  for (let i = 0; i < n; i++) {
    // some constant work
  }
  i = 0;
  while(i < n) {
    i *= n;
  }
  for (i = 0; i < 100; i++) {
    // some constant work
  }

}

Since the work is sequential, we add the values $\Theta(n) + \Theta(\log n) + \Theta(1)$ .
Ignoring lower order terms, the complexity of this function is $\Theta(n)$ .

Nested loops

Python

def fun(n):
    for i in range(n):            # 𝛳(n)
        j = 0
        while j < n:              # 𝛳(log n)
            # some constant work
            j *= 2

JavaScript

function fun(n) {
  for(let i = 0; i < n; i++) {
    let j = 0;
    while(j < n) {
      j *= 2;
    }
  }
}

Since it’s a nested loop,we multiply the values $\Theta(n) * \Theta(\log n)$ .
Therefore the complexity is $\Theta(n \log n)$ .

Nested loops 2

Python

def fun(n):
    for i in range(n):          # 𝛳(n)
        for j in range(n):      # 𝛳(n)
            # some constant work

JavaScript

function fun(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // some constant work
    }
  }
}

The time complexity is $\Theta(n^2)$ .